package com.sunshine.leetcode.easy;

import java.util.HashMap;

/**
 * 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
 * <p>
 * 请你找到并返回这个整数
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：arr = [1,2,2,6,6,6,6,7,10]
 * 输出：6
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/element-appearing-more-than-25-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author WeiHong
 * @date 2020/4/24 9:38
 */
public class FindSpecialInteger {

    /**
     * 1.获取数组长度的25%（即数组长度的1/4）
     * 2.查询大于这个长度的元素
     *
     * @param arr
     * @return
     */
    public static int myFindSpecialInteger(int[] arr) {
        //获取数组长度的25%（即数组长度的1/4）
        int length = arr.length / 4;
        var map = new HashMap<Integer, Integer>(10);
        for (int e : arr) {
            if (0 == length) {
                return e;
            }
            //当前元素e的长度
            Integer len = map.get(e);
            if (null == len) {
                map.put(e, 1);
            } else {
                ++len;
                if (len > length) {
                    return e;
                }
                map.put(e, len);
            }
        }
        return 0;
    }

    /**
     * 由于数组 arr 已经有序，那么相同的数在 arr 中出现的位置也是连续的
     * - 根据arr.length找到超过25%处的下标
     * - 保持固定距离（25%个数）
     * - 如若两个指针所指的数相等及为所求
     *
     * @param arr
     * @return
     */
    public static int findSpecialInteger(int[] arr) {
        int before = arr.length / 4;
        for (int i = 0; before < arr.length; i++, before++) {
            if (arr[i] == arr[before]) {
                return arr[i];
            }
        }
        return arr[arr.length - 1];
    }


}
